package com.leetcode.子串;

import java.util.Deque;
import java.util.LinkedList;

public class lc_239 {
    public static void main(String[] args) {

    }

    //给你一个整数数组 nums，有一个大小为 k
    // 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。
    // 滑动窗口每次只向右移动一位。
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 1) {
            return nums;
        }
        //len为遍历的次数也是res数组的长度
        int len = nums.length - k + 1;
        int num = 0;
        //自定义队列
        myDeque deque = new myDeque();

        //定义出结果数组
        int[] res = new int[len];
        //先将前k个数字加入队列,这时候add已经生效了,保证队头为最大值
        for (int i = 0; i < k; i++) {
            deque.add(nums[i]);
        }
        res[num++] = deque.peek();
        for (int i = k; i < nums.length; i++) {
            //滑动窗口移除最前面的元素
            deque.poll(nums[i - k]);
            //滑动窗口加入最后面的元素
            deque.add(nums[i]);
            //记录最大值
            res[num++] = deque.peek();
        }
        return res;

    }

    class myDeque {
        Deque<Integer> deque = new LinkedList<>();

        //弹出元素时,判断当前元素与队列出口元素是否相等,相等则弹出
        //不相等说明添加元素的时候,删除了前面一定的元素,所以此时实际上还没轮到弹出这个最大的 元素
        void poll(int val) {
            if (!deque.isEmpty() && val == deque.peek()) {
                deque.poll();
            }
        }

        //添加元素时,如果要添加的元素大于队尾元素,就将队尾元素弹出
        //保证队列元素单调递减,比如 5,2,3. 这时候加入4,  就会将 2,3 删除
        void add(int val) {
            while (!deque.isEmpty() && val > deque.getLast()) {
                deque.removeLast();
            }
            deque.add(val);
        }

        //add和poll操作已经保证了队列元素始终为最大值
        int peek() {
            return deque.peek();
        }
    }
}
